package com.skh.stack;

import java.util.Stack;

/**
 * 最小栈
 * created by skh on 2020/3/7
 */
public class MinStack {

	/**
	 * 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
	 *
	 * push(x) -- 将元素 x 推入栈中。
	 * pop() -- 删除栈顶的元素。
	 * top() -- 获取栈顶元素。
	 * getMin() -- 检索栈中的最小元素。
	 * 示例:
	 *
	 * MinStack minStack = new MinStack();
	 * minStack.push(-2);
	 * minStack.push(0);
	 * minStack.push(-3);
	 * minStack.getMin();   --> 返回 -3.
	 * minStack.pop();
	 * minStack.top();      --> 返回 0.
	 * minStack.getMin();   --> 返回 -2.
	 */


	/**
	 * 思路：
	 * 这道题最直接的解法就是我们可以用两个栈，
	 * 一个栈去保存正常的入栈出栈的值，另一个栈去存最小值，也就是用栈顶保存当前所有元素的最小值。
	 *
	 * 存最小值的栈的具体操作流程如下：
	 *
	 * 将第一个元素入栈。
	 *
	 * 新加入的元素如果大于栈顶元素，那么新加入的元素就不处理。
	 *
	 * 新加入的元素如果小于等于栈顶元素，那么就将新元素入栈。
	 *
	 * 出栈元素不等于栈顶元素，不操作。
	 *
	 * 出栈元素等于栈顶元素，那么就将栈顶元素出栈。
	 */
	private Stack<Integer> stack;
	private Stack<Integer> minStack;
	public MinStack() {
		stack = new Stack<>();
		minStack = new Stack<>();
	}

	public void push(int x) {
		stack.push(x);
		if (minStack.isEmpty()) {
			minStack.push(x);
		} else {
			if (x <= minStack.peek()) {
				minStack.push(x);
			}
		}
	}

	public void pop() {
		Integer pop = stack.pop();
		if (minStack.peek() .equals(pop) ) {
			minStack.pop();
		}
	}

	public int top() {
		return stack.peek();
	}

	public int getMin() {
		return minStack.peek();
	}
}
